Search results for "PROBABILISTIC FINITE AUTOMATA"

showing 5 items of 5 documents

Implications of quantum automata for contextuality

2014

We construct zero error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded error probabilistic finite automata (PFAs). Here is a summary of our results: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) space PTMs in polynomial expected time. The same problem can be solvable by a one way Las Vegas (or exact two way) QFA with quantum head in linear (expected) time. There is a promise problem solvable by a Las …

Discrete mathematicsProbabilistic finite automataTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESQuantum automata0102 computer and information sciencesConstruct (python library)Nonlinear Sciences::Cellular Automata and Lattice Gases01 natural sciencesKochen–Specker theoremTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematics0103 physical sciencesQuantum finite automataPromise problem010306 general physicsComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Quantum Finite Multitape Automata

1999

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …

Discrete mathematicsProbabilistic finite automataFinite-state machineNested wordComputer scienceDeterministic context-free grammarTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesAutomatonMobile automatonNondeterministic finite automaton with ε-movesDeterministic finite automatonDFA minimizationRegular languageDeterministic automatonProbabilistic automatonContinuous spatial automatonAutomata theoryQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton
researchProduct

Probabilistic Reversible Automata and Quantum Automata

2002

To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.

Discrete mathematicsProbabilistic finite automataNested wordComputer scienceTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesMobile automatonAutomatonStochastic cellular automatonDeterministic finite automatonDFA minimizationContinuous spatial automatonAutomata theoryQuantum finite automataNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton
researchProduct

Quantum, stochastic, and pseudo stochastic languages with few states

2014

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all th…

FOS: Computer and information sciencesFINITE AUTOMATAClass (set theory)Unary operationFormal Languages and Automata Theory (cs.FL)QUANTUM FINITE AUTOMATACOMPUTATIONAL MODELBINARY ALPHABETSFOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputer Science::Computational ComplexityPROBABILISTIC FINITE AUTOMATAREAL NUMBERUNARY LANGUAGESQuantum finite automataCUT-POINTMathematicsReal numberDiscrete mathematicsQuantum PhysicsFinite-state machineGENERALIZED FINITE AUTOMATAComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)STOCHASTIC SYSTEMSAutomatonSTOCHASTIC LANGUAGESMathematics::LogicProbabilistic automatonComputer Science::Programming LanguagesQUANTUM THEORYUncountable setQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata TheoryGENERALIZED FINITE AUTOMATON
researchProduct

Regularity of one-letter languages acceptable by 2-way finite probabilistic automata

1991

R. Freivalds proved that the nonregular language {0m1m} can be recognized by 2-way probabilistic finite automata (2pfa) with arbitrarily high probability 1-e (e>0). We prove that such an effect is impossible for one-letter languages: every one-letter language acceptable by 2pfa with an isolated cutpoint is regular.

Discrete mathematicsHigh probabilityProbabilistic finite automataComputer scienceProbabilistic automaton
researchProduct